import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 55, 6, 8, 7, 6, 63, 454, 6, 1, 5};
//        mergeSort(arr, 0, arr.length-1);
        quickSort(arr, 0, arr.length-1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static void quickSort(int[] arr, int left, int right) {
        if (right - left <= 0)  return;

        int tempValue = arr[left];
        int leftIndex = left, rightIndex = right;
        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex && arr[rightIndex] >= tempValue) {
                rightIndex--;
            }
            if (leftIndex < rightIndex && arr[rightIndex] < tempValue) {
                arr[leftIndex++] = arr[rightIndex];
            }
            while (leftIndex < rightIndex && arr[leftIndex] <= tempValue) {
                leftIndex++;
            }
            if (leftIndex < rightIndex && arr[leftIndex] > tempValue) {
                arr[rightIndex--] = arr[leftIndex];
            }
        }
        arr[leftIndex] = tempValue;

        quickSort(arr, left, leftIndex-1);
        quickSort(arr, leftIndex+1, right);
    }
//    public static void mergeSort(int[] arr, int left, int right) {
//        if (right - left <= 0)  return;
//
//        int mid = left + (right-left)/2;
//
//        mergeSort(arr, left, mid);
//        mergeSort(arr, mid+1, right);
//
//        mergeArray(arr, left, mid, mid+1, right);
//    }
//    public static void mergeArray(int[] arr, int left, int mid, int midPlus, int right) {
//        int[] newArr = new int[arr.length];
//        System.arraycopy(arr, 0, newArr, 0, arr.length);
//
//        int leftIndex = left, rightIndex = midPlus, indexNow = left;
//        while (leftIndex <= mid || rightIndex <= right) {
//            if (leftIndex > mid) {
//                System.arraycopy(arr, rightIndex, newArr, indexNow, right-rightIndex+1);
//                break;
//            }
//            if (rightIndex > right) {
//                System.arraycopy(arr, leftIndex, newArr, indexNow, mid-leftIndex+1);
//                break;
//            }
//            if (arr[leftIndex] <= arr[rightIndex]) {
//                newArr[indexNow++] = arr[leftIndex++];
//            } else {
//                newArr[indexNow++] = arr[rightIndex++];
//            }
//        }
//        System.arraycopy(newArr, 0, arr, 0, arr.length);
//    }
}
